package tencent_practice;

import structure.ListNode;

import java.util.Arrays;

/**
 * 排序链表
 * 给出链表头节点，将其按照升序排列并返回排序后的结果
 */
public class Tencent_148_sortList {
    /**
     * 借用一个数组，把所有的节点都存起来，将数组排序，再把数组转化成链表
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        int len = 0;
        ListNode curr = head;
        while (head != null) {
            len++;
            head = head.next;
        }
        int[] temp = new int[len];
        for (int i = 0; i < len; i++) {
            temp[i] = curr.val;
            curr = curr.next;
        }
        Arrays.sort(temp);
        ListNode helpNode = new ListNode();
        ListNode node = helpNode;
        for (int i = 0; i < len; i++) {
            node.next = new ListNode(temp[i]);
            node = node.next;
        }
        return helpNode.next;
    }
}
